/*
	解法：暴力枚举 或 移动匹配 或 KMP
	为什么：移动匹配
			将字符串 s 拼接两次，形成 s + s，再去掉首尾字符，看中间是否还包含原始字符串 s
			如果包含，就说明它是由某个子串重复构成的。
	时间复杂度：O(n)，空间复杂度：O(n)
 */

#include <iostream>
#include <string>

using namespace std;

class Solution
{
public:
	bool repeatedSubstringPattern(string s)
	{
		string t = s + s;
		string sub = t.substr(1, t.length() - 2);
		
		size_t pos = sub.find(s);
		
		//string::npos 是C++ std::string 类中的一个静态常量，它是一个表示字符串中“不存在的位置”或“未找到匹配”的特殊值。 
		//npos 通常被用作 std::string 的成员函数（如 find()、rfind()）的返回值，表示搜索操作失败。 
		if (pos != string::npos)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
};

int main()
{
	Solution solution;
	string s;
	
	cout << "请输入字符串：" << endl;
	cin >> s;
	
	bool result = solution.repeatedSubstringPattern(s);
	
	if (result)
	{
		cout << "true" << endl;
	}
	else
	{
		cout << "false" << endl;
	}
	
	return 0;
}


